#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
 
typedef struct treeNode
{
	
	int value;
	treeNode *left, *right;
	treeNode *parent;
	int ales; //1-vizitat
	char color;
	treeNode *r,*l;
	treeNode *p;
}treeNode;
treeNode *root;
struct treeNode *grandparent(treeNode *n)
{
	if((n!=NULL) && (n->p!=NULL))
		return n->p->p;
	else
		return NULL;
}
struct treeNode *uncle(treeNode *n)
{
	treeNode *g=grandparent(n);
	if(g==NULL)
		return NULL;//daca nu exista bunic nu exista nici unchi
	if(n->p==g->l)
		return g->r;
	else
		return g->l;
}

void display(treeNode *nou,int level);
void insert_case1(treeNode *&root_rb,treeNode *n);
void insert_case2(treeNode *&root_rb,treeNode *n);
void insert_case3(treeNode *&root_rb,treeNode *n);
void insert_case4(treeNode *&root_rb,treeNode*n);
void insert_case5(treeNode *&root_rb,treeNode *n);
int height(treeNode *subroot);
void sortare(int *ok, int n);
treeNode *creare_nod(int i, int j, int *v,treeNode *parent);
void repetare_el(int *v, int *ok, int n, int &l);
int arbore_complet(treeNode *subroot, int h, int n);
void calepreferata(treeNode *subroot, treeNode **pref, int &i);
void matrice_preordine(treeNode *subroot, treeNode ***mat, treeNode **pref, int &j, int *vec);


void display_rb(treeNode *nou,int level);
void linie(treeNode ***mat, int *vec, int j, treeNode **roots);
void rbInsert(treeNode *&subroot, treeNode *z);
void rightRotate( treeNode *&subroot, treeNode *y);
void leftRotate(treeNode *&subroot,treeNode *x);

void TANGO_TREE(treeNode **roots, int j, treeNode ***mat);
treeNode *cautare(int val);

void main()
{
	int nr_nod;
	int l;
	int v[100];
	int ok[100];
	printf("introduceti numarul de noduri:");
	scanf("%d", &nr_nod);
	for(int i=0;i<nr_nod;i++)
	{
		printf("introduceti valoarea nodului:");
		scanf("%d", &v[i]);
	}
	repetare_el(v,ok,nr_nod, l);
	sortare(ok,l);
	root=creare_nod(0,l, ok,0);
	display(root, 0);
	int h=height(root);
	if(arbore_complet(root, h, nr_nod))
		printf("Arborele este complet.\n");
	else
		{	
			printf("Arborele nu este complet. Mai incercati odata.\n");
			return;
	}
	system("pause");
	system("cls");
	treeNode *pref[100];
	int p;// p=nr de elemente de pe o linie a matricei pref
	/*calepreferata(root, pref, p);
	for(int k=0;k<p;k++)
		printf("%d\n", pref[k]->value);*/
	treeNode ***mat;
	mat=(treeNode***)malloc(sizeof(treeNode**)*100);
	for(int k=0;k<100;k++)
		mat[k]=(treeNode**)malloc(sizeof(treeNode*)*100);
	int vec[100];
	int j=0;
	matrice_preordine(root,mat, pref, j, vec);
	printf("MATRICEA DE CAI PREFERATE ESTE:\n");
	for(int i=0;i<j;i++)
	{
		for(int k=0;k<vec[i];k++)
		printf("%d ", mat[i][k]->value);
		printf("\n");	
	}
	system("pause");
//urmeaza stocarea cailor preferate in arbori auxiliar-ARBORI ROSU_NEGRU
	treeNode *radacina;
	treeNode *roots[100];
	linie(mat, vec,j, roots);
	for(int h=0;h<j;h++)
		printf("%d, ", roots[h]->value);
	system("pause");
	TANGO_TREE(roots, j, mat);
	display_rb(root, 0);
	int val;
	printf("Introduceti valoare pe care o cautati:");
	scanf("%d", &val);
	treeNode *gasit=cautare(val);
	if(gasit)
		printf("valoarea cautata %d a fost gasita\n", gasit->value);
	else
		printf("valoarea cautata nu a fost gasita\n");


}

void repetare_el(int *v, int *ok, int n, int &l)
{
	int p;
	l=1;
	ok[0]=v[0];
	for(int i=1;i<n;i++)
	{
		p=0;
		for(int j=0;j<i;j++)
		{
			if(v[i]!=v[j])
				p++;
		}
		
		if(p==i)
		{
			ok[l]=v[i];
			l++;
		}
	}

}
void sortare(int *ok, int n)
{
	int bla;
	do
	{
		bla=0;
		for(int i=0;i<n-1;i++)
			if(ok[i]>ok[i+1])
			{
				int aux=ok[i];
				ok[i]=ok[i+1];
				ok[i+1]=aux;
				bla=1;
			}
	}while(bla);
}
treeNode* creare_nod(int i, int j, int *v,treeNode *parent)
{
	if(i==j)
		return NULL;
	int mid=(i+j)/2;
	treeNode *nou=(treeNode*)malloc(sizeof(treeNode));
	nou->value=v[mid];
	nou->parent=parent;
	nou->l=NULL;
	nou->r=NULL;
	nou->ales=0;
	nou->color='r';
	nou->p=NULL;
	nou->left=creare_nod(i, mid, v,nou);
	nou->right=creare_nod(mid+1, j, v,nou);
	return nou;
}
void display(treeNode *nou,int level)
{
	int i;
	if(nou!=NULL)
	{
		display(nou->right,level+1);
		printf("\n");
		for(i=0;i<level;i++)
			printf(" ");
		printf("%d\n",nou->value);
		display(nou->left,level+1);

	}
}
int height(treeNode *subroot)
{
	if(subroot==NULL)
	{
		return 0;
	}
	if(subroot->left!=NULL || subroot->right!=NULL)
	{
		int hs=height(subroot->left);
		int hd=height(subroot->right);
		if(hs<hd)
			return hd+1;
		else
			return hs+1;
	}
	return 0;
}
int arbore_complet(treeNode *subroot, int h, int n)
{
	int count=1;
	for(int i=0;i<=h;i++)
		count=count*2;
	if(n==count-1)
		return 1;
	else
		return 0;
}
void calepreferata(treeNode *subroot, treeNode **pref, int &i)
{
	i=0;
	if(subroot==NULL)
		return;
	subroot->ales=1;
	pref[i]=subroot;
	i++;
	subroot=subroot->left;
	while(subroot)
	{
		if(subroot->value==subroot->parent->left->value)
		{
			subroot->ales=1;
			pref[i]=subroot;
			i++;
			subroot=subroot->right;
		}
		else
			if(subroot->value==subroot->parent->right->value)
		{
			subroot->ales=1;
			pref[i]=subroot;
			i++;
			subroot=subroot->left;
		}
	}
}
void matrice_preordine(treeNode *subroot, treeNode ***mat, treeNode **pref, int &j, int *vec)
{
	int i;
	if(subroot==NULL)
		return;
	if(subroot->ales==0)
	{
		calepreferata(subroot, pref, i);
		vec[j]=i;
		for(int k=0;k<i;k++)
		{
			mat[j][k]=(treeNode*)malloc(sizeof(treeNode));
			mat[j][k]=pref[k];
		}
		j++;
	}
	matrice_preordine(subroot->left, mat, pref, j, vec);
	matrice_preordine(subroot->right, mat, pref, j, vec);
}
void insert_case1(treeNode *&root_rb,treeNode *n)//recolorare in negru
{
	if(n->p==NULL)
		n->color='b';
	else 
		insert_case2(root_rb, n);
}
void insert_case2(treeNode*&root_rb,treeNode*n)//arbore ok
{
	if(n->p->color=='b')
		return;
	else
		insert_case3(root_rb, n);
}
void insert_case3(treeNode *&root_rb,treeNode *n)//parintele si unchiul sunt rosii; recolorare
{
	treeNode *u=uncle(n);
	treeNode *g;
	if((u!=NULL)&&(u->color=='r'))
	{
		n->p->color='b';
		u->color='b';
		g=grandparent(n);
		g->color='r';
		insert_case1(root_rb,n);
	}
	else
		insert_case4(root_rb, n);
}
void insert_case4(treeNode*&root_rb,treeNode *n)
{
	treeNode *g=grandparent(n);
	if((n==n->p->r)&&(n->p==g->l))
	{
		leftRotate(root_rb, n->p);
		n=n->l;
	}
	else
		if((n==n->p->l)&&(n->p==g->r))
		{
			rightRotate(root_rb, n->p);
			n=n->r;
		}
	insert_case5(root_rb,n);
}
void insert_case5(treeNode *&root_rb,treeNode *n)
{
	treeNode *g=grandparent(n);
	n->parent->color='b';
	g->color='r';
	if(n==n->p->l)
		rightRotate(root_rb,g);
	else
		leftRotate(root_rb,g);
}
void display_rb(treeNode *nou,int level)
{
	int i;
	if(nou!=NULL)
	{
		display_rb(nou->r,level+1);
		printf("\n");
		for(i=0;i<level;i++)
			printf(" ");
		printf("%d\n",nou->value);
		display_rb(nou->l,level+1);

	}
}
void leftRotate(treeNode *&subroot,treeNode *x)
{
	treeNode *y;
	y = x->r;  //Set y
	x->r = y->l; // Turn y's left subtree into x's right subtree
	if( y->l != NULL)
		y->l->p = x; //Bridge the y's left sublink
	y->p = x->p; //Bridge x's old parent and y's parent
	if( x->p == NULL)
		subroot = y;
	else 
		if( x->value == x->p->l->value)
			 x->p->l = y; //Bridge x's old parent's left or right child
		else x->p->r = y;
	y->l = x; //put x on y's left
	x->p = y; //Take care of x's parent

return;
}
void rightRotate( treeNode *&subroot, treeNode *y){
 treeNode *x;
x = y->l; //set x
y->l = x->r; //Turn x's right subtree into y's left subtree
if ( x->r != NULL){
    x->r->p = y;
}
x->p= y->p; //Bridge y's old parent and x's parent
if( y->p == NULL){
    subroot = x;
} 
else if( y->value == y->p->l->value){
    y->p->l = x; //Bridge y's old parent's left or right child
}
else y->p->r = x;
x->r = y; //put y on x's right
y->p = x; //Take care of y's parent

return;

}
void rbInsert(treeNode *&subroot, treeNode *z){
treeNode *x = subroot;
treeNode *y;
if ( subroot == NULL ){
    subroot = z;
    subroot->color = 'b';
    return;
}
while ( x != NULL){
    y = x;
	if ( z->value < x->value){
        x = x->l;
    }
    else x = x->r;
}
z->p = y;
if ( y == NULL){
    subroot = z;
}
else if( z->value < y->value ){
    y->l = z;
}
else y->r = z;
//rbInsertFix(subroot,z);
insert_case1(subroot, z);
return;
}

void linie(treeNode ***mat, int *vec,int j, treeNode **roots)
{
	//radacinile arborilor rosu-negru
	for(int h=0;h<j;h++)
	{
		treeNode *subroot=NULL;
		for(int k=0;k<vec[h];k++)
			rbInsert(subroot, mat[h][k]);
		roots[h]=subroot;
		system("pause");
		display_rb(subroot, 0);
	}
}

void TANGO_TREE(treeNode **roots, int j, treeNode ***mat)
{
	root=roots[0];
	for(int i=1;i<j;i++)
	{
		treeNode *aux=mat[i][0]->parent;
		if(roots[i]->value>aux->value)
		{
			while(aux->r!=NULL && roots[i]->value>aux->value)
				aux=aux->r;
			if(roots[i]->value<aux->value)
			{
				roots[i]->p=aux;
				aux->l=roots[i];
			}
			else
			{
				roots[i]->p=aux;
				aux->r=roots[i];
			}
		}
		else
		{
			while(aux->l!=NULL && roots[i]->value<aux->value)
				aux=aux->l;
			if(roots[i]->value<aux->value)
			{
				roots[i]->p=aux;
				aux->l=roots[i];
			}
			else
			{
				roots[i]->p=aux;
				aux->r=roots[i];
			}
		}
	}
}

treeNode *cautare(int val)
{
	treeNode *p=root;
	while(p!=NULL)
	{
		if(val==p->value)
			return p;
		if(val<p->value)
			p=p->l;
		else
			p=p->r;
	}
	return 0;
}